Arbres AVL

G. Adelson-Velskii et E. M. Landis, An Algorithm for the Organization of Information. Soviet Mathematics Doklady, 3:1259–1263, 1962

Principe

Les arbres AVL sont des arbres binaires de recherche qui garantissent qu'aucun noeud de l'arbre n'a un déséquilibre en dehors de l'intervalle [-1,1].

Le déséquilibre d'un noeud est la différence de hauteur entre ses sous-arbres gauches et droits.

Pour les mettre en oeuvre, il faut - à chaque insertion et suppression -

• mesurer le déséquilibre de chaque noeud traversé

• corriger ce déséquilibre avec des opérations locales

avec une complexité constante par noeud traversé.

Mesurer le déséquilibre

Le déséquilibre d'un noeud est défini à partir de la hauteur de ses enfants droit et gauche

def equilibre(R):    
    if R == None: return 0
    else: return hauteur(R.gauche) - hauteur(R.droite) 

Calculer cette hauteur peut se faire récursivement

def hauteur(R):
    if R == None: return 0
    return max(hauteur(R.gauche),
               hauteur(R.droite)) + 1

Mais avec une complexité $\Theta(n)$ avec $n$ le nombre d'éléments dans le sous-arbre dont R est la racine.

Pour rendre ce calcul plus efficace, on stocke la hauteur comme un attribut supplémentaire de chaque noeud

class Noeud:
    def __init__(self,val):
        self.clef = val
        self.droite = None
        self.gauche = None
        self.hauteur = 1
    def __str__(self): 
        return "{}".format(self.clef)

La fonction hauteur a maintenant une complexité $\Theta(1)$

def hauteur(R):
    return R.hauteur if R else 0

Mais il faut maintenir la valeur de l'attribut à jour lors de toute opération susceptible de le modifier (insertion, suppression)

def calculer_hauteur(R):
    if R:
        R.hauteur = max( hauteur(R.gauche), 
                        hauteur(R.droite)) + 1

Corriger le déséquilibre

L'opération de base pour corriger un déséquilibre est la rotation, gauche ou droite. Prenons par exemple l'arbre suivant

R = X = Noeud('X');        
A = X.gauche = Noeud('A'); Y = X.droite = Noeud('Y'); 
B = Y.gauche = Noeud('B'); C = Y.droite = Noeud('C')
import include.helpers as h; h.afficher_arbre_binaire(X)

Pour un arbre binaire de recherche, A < X < B < Y < C.

La rotation gauche consiste à faire de Y - l'enfant droite de X - la racine, tout en maintenant la propriété d'arbre de recherche A < X < B < Y < C.

def rotation_gauche(x):
    y = x.droite
    x.droite = y.gauche
    y.gauche = x
    return y

R = rotation_gauche(R)
h.afficher_arbre_binaire(R)

La rotation droite est l'opération inverse

def rotation_droite(x):
    y = x.gauche; x.gauche = y.droite; y.droite = x
    return y

R = rotation_droite(R)
h.afficher_arbre_binaire(R)

Quel est l'effet de ces rotations sur les hauteurs

• des noeuds X et Y?
• des sous-arbres de racine A, B et C?

Pour A, B et C, la rotation n'a aucun effet. Pour les noeuds X et Y, il faudra le recalculer. Les fonctions de rotations sont donc

def rotation_droite(x):
    y = x.gauche; x.gauche = y.droite; y.droite = x
    calculer_hauteur(x); calculer_hauteur(y)
    return y

def rotation_gauche(x):
    y = x.droite; x.droite = y.gauche; y.gauche = x
    calculer_hauteur(x); calculer_hauteur(y)
    return y

Assignons des hauteurs qui déséquilibrent l'arbre vers la droite au noeud X

def afficher_hauteur(R): 
    return "{} h{} e{}".format(R.clef,hauteur(R),equilibre(R))
Noeud.__str__ = afficher_hauteur

A.hauteur = 4; B.hauteur = 5; C.hauteur = 5;
calculer_hauteur(Y); calculer_hauteur(X)

h.afficher_arbre_binaire(R)

Appliquons la rotation gauche.

R = rotation_gauche(R); h.afficher_arbre_binaire(R)

L'équilibre est revenu dans la plage [-1,1] pour tous les noeuds.

Est-ce toujours le cas? Cela dépend de l'équilibre de départ du noeud Y

Pour Y déséquilibré vers la droite,

h.afficher_arbre_binaire(R)

La rotation rétablit un équilibre parfait

R = rotation_gauche(R); h.afficher_arbre_binaire(R)

Pour Y déséquilibré vers la gauche,

h.afficher_arbre_binaire(R)

La rotation gauche ne rétablit par l'équilibre

R = rotation_gauche(R); h.afficher_arbre_binaire(R)

Il est donc indispensable que le noeud Y soit équilibré ou penche à droite avant d'effectuer la rotation gauche de X.

On peut le garantir en effectuant une rotation droite de Y quand celui-ci penche à gauche. Pour visualiser cette rotation, donnons des enfants à 'B'

h.afficher_arbre_binaire(R);

Effectuons la rotation droite de Y

Y = X.droite = rotation_droite(Y)
h.afficher_arbre_binaire(R)

Puis la rotation gauche de X

R = rotation_gauche(R); h.afficher_arbre_binaire(R)

Le résultat est équilibré, et le serait également si C avait un déséquilibre de $\pm 1$ (avec D ou E de hauteur 3)

L'opération complète d'équilibrage d'un noeud R s'écrit donc

def equilibrer(R):
    assert(R != None)
    eq = equilibre(R)
    if eq < -1:
        if equilibre(R.droite) > 0:
            R.droite = rotation_droite(R.droite)
        R = rotation_gauche(R)    
    elif eq > 1:
        if equilibre(R.gauche) < 0:
            R.gauche = rotation_gauche(R.gauche)
        R = rotation_droite(R)
    else:
        calculer_hauteur(R)
    return R

Restent à déterminer

• quand appliquer cet équilibrage ?

• à quels noeuds l'appliquer ?

• dans quel ordre traiter ces noeuds ?

La réponse à ces questions est

• Quand? - Après chaque opération qui peut modifier la hauteur des sous-arbres. Donc après insertion et suppression

• Quels noeuds? - Tous les noeuds traversés par l'opérations, i.e. aux ancêtres des noeuds insérés ou supprimés

• Quel ordre? - Du noeud le plus profond à la racine

Insertion

Le code de l'insertion est quasiment identique à celui d'un arbre binaire de recherche. La seule différence est la dernière ligne qui retourne R équilibré.

Appeler equilibrer en retour de récursion permet d'équilibrer les noeuds de la feuille à la racine.

def inserer(R,val):
    if R == None:
        return Noeud(val)
    else:
        if val < R.clef:
            R.gauche = inserer(R.gauche,val)
        elif val > R.clef:
            R.droite = inserer(R.droite,val)
        else: # val == R.data
            pass
        return equilibrer(R)

Visualizons l'insertion dans un arbre AVL

R = None; R = inserer(R,1); h.afficher_arbre_binaire(R)

R = inserer(R,2); h.afficher_arbre_binaire(R)

R = inserer(R,3); h.afficher_arbre_binaire(R)

R = inserer(R,4); h.afficher_arbre_binaire(R)

R = inserer(R,5); h.afficher_arbre_binaire(R)

R = inserer(R,6); h.afficher_arbre_binaire(R)

R = inserer(R,7); h.afficher_arbre_binaire(R)

Suppression du minimum

def supprimer_minimum(R):
    if R == None: raise IndexError()
    
    if R.gauche:
        R.gauche = supprimer_minimum(R.gauche)
        return equilibrer(R)
    else:
        return R.droite

R = supprimer_minimum(R); h.afficher_arbre_binaire(R)

R = supprimer_minimum(R); h.afficher_arbre_binaire(R)

R = supprimer_minimum(R); h.afficher_arbre_binaire(R)

R = supprimer_minimum(R); h.afficher_arbre_binaire(R)

Suppression d'un élément

def supprimer(R,val):
    if R == None: return R
    elif val < R.clef: 
        R.gauche = supprimer(R.gauche,val)
    elif val > R.clef:
        R.droite = supprimer(R.droite,val)
    else: # val == R.clef
        if   R.gauche == None: return R.droite
        elif R.droite == None: return R.gauche
        else: # sous-arbres des deux côtés
            tmp = plus_petit_noeud(R.droite)
            R.droite = supprimer_minimum(R.droite)
            tmp.gauche = R.gauche; tmp.droite = R.droite
            R = tmp
    return equilibrer(R)    

def plus_petit_noeud(R):
    assert(R != None)
    if R.gauche: return plus_petit_noeud(R.gauche)
    else:        return R

R = None
for i in range(1,16): R = inserer(R,i); 
h.afficher_arbre_binaire(R)

R = supprimer(R,4); 

h.afficher_arbre_binaire(R)

R = supprimer(R,5);

h.afficher_arbre_binaire(R)

R = supprimer(R,6); 

h.afficher_arbre_binaire(R)

R = supprimer(R,2);

h.afficher_arbre_binaire(R)

R = supprimer(R,3);

h.afficher_arbre_binaire(R)

R = supprimer(R,7); 

h.afficher_arbre_binaire(R)

ASD1 Notebooks on GitHub.io © Olivier Cuisenaire, 2018